package leetcode;
/**
 * 94.二叉树的中序遍历
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 */
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
public class Num_94 {
    /** 方法一：递归 **/
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        //边界条件
        if(root == null){
            return list;
        }
        //先递归遍历左子树
        inorderTraversal(root.left);
        //再添加根节点
        list.add(root.val);
        //递归遍历右子树
        inorderTraversal(root.right);
        return list;
    }

    /** 方法二：迭代 **/
    public List<Integer> inorderTraversal2(TreeNode root){
        List<Integer> list = new ArrayList<>();
        //边界条件
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            //不用先弹出栈顶元素，而是先把左子树的左子树也全部压入栈中
            while(cur != null){
                stack.offerFirst(cur);
                cur = cur.left;
            }
            //此时cur==null,说明左边走到了尽头
            cur = stack.pollFirst();
            list.add(cur.val);
            //再继续访问右子树
            cur = cur.right;
        }
        return list;
    }
}
